package com.HW.Search;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @ClassName : test
 * @Author : kele
 * @Date: 2023/10/29 11:20
 * @Description :战场索敌
 *
 * 有一个大小是N*M的战场地图，被墙壁#分隔成大小不同的区域，上下左右四个方向相邻的空地 属于同一个区域，
 * 只有空地上可能存在敌人'E",请求出地图上总共有多少区域里的敌人数小于K。
 */
public class TLockEnemy {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        while (in.hasNext()) { // 注意 while 处理多个 case
            String s1 = in.nextLine();
            String[] s = s1.split(" ");
            int n = Integer.parseInt(s[0]);
            int m = Integer.parseInt(s[1]);
            int k = Integer.parseInt(s[2]);

            char[][] soldier = new char[n][];
            for (int i = 0; i < n; i++) {
                String line = in.nextLine();
                soldier[i] = line.toCharArray();
            }

            handle(n,m,k,soldier);

        }

//        String string = "..#EE,E.#E.,###..";
//        String[] str = string.split(",");
//        char[][] soldier = new char[str.length][str[0].length()];
//
//        for (int i = 0; i < str.length; i++) {
//            soldier[i] = str[i].toCharArray();
//        }
//        handle(3, 5, 2, soldier);
/*
3 5 3
..#EE
E.#E.
###..
 */


    }

    public static void handle(int n, int m, int k, char[][] soldier) {

        boolean[][] isValid = new boolean[n][m];


        int num = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {

                if (soldier[i][j] == 'E' && !isValid[i][j]) {
                    num = dfs(i, j, soldier, isValid) < k ? num + 1 : num;
                }
            }
        }
        System.out.println(num);


    }

    public static int dfs(int n, int m, char[][] soldier, boolean[][] isValid) {

        Queue<Integer[]> queue = new LinkedList<>();
        int num = 1;
        int[][] direct = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        queue.add(new Integer[]{n, m});
        isValid[n][m] = true;

        while (!queue.isEmpty()) {

            Integer[] poll = queue.poll();

            for (int[] ints : direct) {
                int i = poll[0] + ints[0];
                int j = poll[1] + ints[1];

                if (i >= 0 && j >= 0 && i < soldier.length && j < soldier[0].length) {

                    if (soldier[i][j] != '#' && !isValid[i][j]) {
                        if (soldier[i][j] == 'E') num++;
                        queue.add(new Integer[]{i, j});
                    }

                    isValid[i][j] = true;
                }
            }
        }

        return num;
    }
}
